/** \file    segmcomb.h
  * \brief   Combination of two segmentations.
  * \date    2002
  * \author  Fedor Chelnokov
  * \version $Header: /home/cscom1r4/cvsroot/cs/include/imglib/segmcomb.h,v 1.4 2006/01/15 07:31:32 cscom1r4 Exp $
  */

#ifndef _segmcomb_h_
#define _segmcomb_h_

#include <utility>
#include <map>
#include <vector>
#include <limits>
#include "neighbor.h"
#include "xtd/group.h"

#include "segmbasic.h"

namespace img {

//C - container capable to random indexing (std::vector) and value_type having integer 'pixels' member

///builds intersection (fine segmentation) of two segmentations
///!warning: this function is fast but occasionally may produce not-connected segments 
///\return formed number of segments
template <class R, class RI>
size_t intersect(const R& segm1, const R& segm2, RI& index_map);
///optionally returnes pixel count for each new segment
///\return formed number of segments
template <class R, class RI, class C>
size_t intersect(const R& segm1, const R& segm2, RI& index_map, C *counters);

//same as intersect but with guaranty of connectedness of segments
template <class R, class RI>
size_t intersect2(const R& segm1, const R& segm2, RI& index_map);
//here C::value_type should be true descendant of merge_patch<>
//if piece_vec!=0 then index_map will not be rewriten second time with roots of pieces
template <class R, class RI, class C>
size_t intersect2(const R& segm1, const R& segm2, RI& index_map, C *piece_vec);

///subdivides a segment from segm1 only if its parts are large enough
///(large that one third part of mean segment size of intersect() result)
///\return formed number of segments
///\param separable_sg_size - subsegments with size less than it should not appear (default-implicit calculation)
template <class R, class RI>
size_t dominant_intersect(const R& segm1, const R& segm2, RI& index_map, size_t separable_sg_size=0);

///typical superclass of objects in C for vmerge_small
template <class T=size_t>
struct merge_patch: public segm_piece<T> {
	parent_type merge_with;			///< used during search for biggest neighbour
};

/**virtually (modifying only 'piece_vec' but not 'subsegm') merges too small segments of 'subsegm'
 * not crossing 'segm' bounds.
 * \param piece_vec - information about each subsegment (in subsegm)
 * C also requires the same as in xtd::group, and also 'merge_with' member
 * !information in not root pieces becomes inconsistent.
 * If in subsegm there are indexes beyound piece_vec range then areas with these indexes are ignored and not merged.
 */
template <class R, class RI, class C>
void vmerge_small(const R& segm, const RI& subsegm, C &piece_vec, size_t separable_sg_size);

///executes merge_with direction if pixels at the moment before merge still less than 'p'
template <class C>
void do_merge_with(C &piece_vec, size_t p = std::numeric_limits<size_t>::max());

///returns true if there are at least one root patch with pixels less than 'p'
///(and there are other root patches, that is found small root patch is not alone)
template <class C>
bool are_there_small_patch(const C &c, size_t p);

/////////////////////////////
// template implementation //
/////////////////////////////

struct dummy_pixels {
	int pixels;
};
typedef std::vector<dummy_pixels> dummy_pixels_vector;

template <class R, class RI>
size_t intersect(const R& segm1, const R& segm2, RI& index_map)
{
	return intersect<R,RI,dummy_pixels_vector>(segm1, segm2, index_map, 0);
}

template <class R, class RI, class C>
size_t intersect(const R& segm1, const R& segm2, RI& index_map, C *counters)
{
	size_t w=segm1.width(), h=segm1.height();
	assert(w==segm2.width() && h==segm2.height());
	assert(w==index_map.width() && h==index_map.height());

	typedef RI::elem_type index;
	index unused_index = 0;
	R::const_iterator si1(segm1.begin());
	R::const_iterator si2(segm2.begin());
	RI::iterator ii(index_map.begin());

	//translation table from a pair of source segment identifiers into segment index in the combined segmentation
	typedef std::pair<R::elem_type, R::elem_type>	id_pair;
	typedef std::pair<index, int>					val_pair; //first-index of new segment, second-its pixel count
	typedef std::map<id_pair, val_pair>				trans;
	typedef trans::value_type						trans_value;
	typedef std::pair<trans::iterator, bool>		trans_ins_pair;
	trans trans_table;

	for ( ; si1 != segm1.end(); ++si1, ++si2, ++ii) {
		trans_value v(id_pair(*si1,*si2), val_pair(unused_index,1));
		trans_ins_pair p(trans_table.insert(v));
		if (p.second) {
			//insertion occurred
			++unused_index;
		} else {
			++p.first->second.second;
		}
		*ii = p.first->second.first;
	}

	if (counters) {
		counters->resize(unused_index);
		trans::iterator i = trans_table.begin();
		for ( ; i != trans_table.end(); ++i) {
			(*counters)[i->second.first].pixels = i->second.second;
		}
	}
	return trans_table.size();
}

template <class R, class RI>
size_t intersect2(const R& segm1, const R& segm2, RI& index_map)
{
	typedef std::vector< merge_patch<> > piece_vec_type;
	return intersect2<R,RI,piece_vec_type>(segm1, segm2, index_map, 0);
}

///piece checker for double segmentation as source
template <class R1, class R2 = R1>
class double_checker
{
public:
	double_checker(R1 & r1, R2 & r2) : _r1(r1), _r2(r2) {}
	bool top(size_t x, size_t y) const
		{ return _r1(x,y-1) == _r1(x,y) && _r2(x,y-1) == _r2(x,y); }
	bool left(size_t x, size_t y) const
		{ return _r1(x-1,y) == _r1(x,y) && _r2(x-1,y) == _r2(x,y); }
	bool top_left(size_t x, size_t y) const
		{ return _r1(x-1,y-1) == _r1(x,y) && _r2(x-1,y-1) == _r2(x,y); }
	bool top_right(size_t x, size_t y) const
		{ return _r1(x+1,y-1) == _r1(x,y) && _r2(x+1,y-1) == _r2(x,y); }
private:
	R1 &_r1;
	R2 &_r2;
};

template <class R1, class R2>
inline double_checker<R1, R2> get_double_checker(R1 & r1, R2 & r2)
	{ return double_checker<R1, R2>(r1, r2); }

template <class R, class RI, class C>
size_t intersect2(const R& segm1, const R& segm2, RI& index_map, C *piece_vec)
{
	typedef C piece_vec_type;
	piece_vec_type my_piece_vec;
	if (!piece_vec)
		piece_vec = &my_piece_vec;
	else
		piece_vec->clear();

	segmbasic4(index_map, *piece_vec, double_checker<const R>(segm1, segm2));

	if (piece_vec == &my_piece_vec)
		rewrite(index_map, my_piece_vec);

	return xtd::root_count(*piece_vec);
}

template <class R, class RI>
size_t dominant_intersect(const R& segm1, const R& segm2, RI& index_map, size_t separable_sg_size)
{
	size_t w=segm1.width(), h=segm1.height();
	typedef std::vector< merge_patch<> > piece_vec_type;
	piece_vec_type piece_vec;
	intersect2(segm1, segm2, index_map, &piece_vec);
	size_t tol = separable_sg_size ? 
		separable_sg_size : 7U;//std::max(7U, (w * h) / (piece_vec.size() * 3));
	vmerge_small(segm1, index_map, piece_vec, tol);

	rewrite(index_map, piece_vec);

	return xtd::root_count(piece_vec);
}

template <class R, class RI, class C>
void vmerge_small(const R& segm, const RI& subsegm, C &piece_vec, size_t separable_sg_size)
{
	size_t w = segm.width(), h = segm.height();
	assert(w == subsegm.width() && h == subsegm.height());
	rect<size_t> frame(0, 0, w, h);
	typedef C::value_type piece;

	//pass(es) of segmentation image: repetitive merging too small subsegments with theirs neighbours
	//only inside original segments
	while(are_there_small_patch(piece_vec, separable_sg_size)) {
		//clear merge_with
		C::iterator piece_vec_it;
		for (piece_vec_it = piece_vec.begin(); piece_vec_it != piece_vec.end(); ++piece_vec_it)
			piece_vec_it->merge_with = piece::no_parent_value();

		bool merge_prepared = false;
		RI::const_iterator ii(subsegm.begin());
		for ( ; ii != subsegm.end(); ++ii) {
			RI::elem_type v = *ii;
			if (v < 0 || v >= piece_vec.size())
				continue;
			size_t my_ridx = xtd::find_root_idx(piece_vec, v);
			piece &my_root = piece_vec[my_ridx];
			if (my_root.pixels >= separable_sg_size) 
				continue;
			const size_t x = ii.x();
			const size_t y = ii.y();
			//number of pixels in already found potential siubject to parent with
			int potential_pixels = my_root.merge_with == piece::no_parent_value() ?
				0 : xtd::find_root(piece_vec, my_root.merge_with).pixels; 
			int big_brother_ridx;
			int i;
			for (i = 0; i != full_4nei; ++i) {
				const point<size_t> n(neighbor4[i].x + x, neighbor4[i].y + y);
				if (frame.inside(n) && //-1 will be outside too
					segm(x,y) == segm[n] &&
					(v = subsegm[n], v >= 0 && v < piece_vec.size()) &&
					(big_brother_ridx=xtd::find_root_idx(piece_vec, v)) != my_ridx && 
					piece_vec[big_brother_ridx].pixels > potential_pixels) 
				{
					break;
				}
			}
			if (i == full_4nei) 
				continue;
			my_root.merge_with = big_brother_ridx;
			merge_prepared = true;
		}

		if (!merge_prepared)
			break;

		//group each segment with last merge_with
		do_merge_with(piece_vec, separable_sg_size);
	};
}

///relabel = (segmbasic4 + vmerge_small + rewrite), gives to disjoint areas distinctive labels
template <class R, class RI, class SC>
size_t relabel_eliminate_small(const R& segm, RI& index_map, SC& segm_checker, size_t separable_sg_size)
{
	std::vector< merge_patch<> > piece_vector;
	segmbasic4(index_map, piece_vector, segm_checker);
	vmerge_small(segm, index_map, piece_vector, separable_sg_size);
	rewrite(index_map, piece_vector);
	return xtd::root_count(piece_vector);
}

template <class C>
void do_merge_with(C &piece_vec, size_t pmin)
{
	typedef C::value_type piece;
	size_t idx;
	for (idx = 0; idx != piece_vec.size(); ++idx) {
		piece &p = piece_vec[idx];
		if (p.merge_with == piece::no_parent_value())
			continue;
		if (xtd::find_root(piece_vec, idx).pixels >= pmin)
			continue;
		xtd::union_sets(piece_vec, idx, p.merge_with);
	}
}

template <class C>
inline bool are_there_small_patch(const C &c, size_t p)
{
	C::const_iterator i(c.begin());
	int root_patch_found = 0;
	bool small_patch_found = false;
	for (; i != c.end(); ++i)  {
		if (i->is_root()) { 
			++root_patch_found;
			if (i->pixels < p)
				small_patch_found = true;
			if (small_patch_found && root_patch_found >= 2)
				return true;
		}
	}
	return false;
}

} //namespace img

#endif //_segmcomb_h_
